//
// Created by Lenovo on 2025/11/24.
//

#include "Dijksta.h"

void Dijksta(const MGraph *graph, int start, int dist[], int path[]) {
    int* marked = (int*)malloc(sizeof(int)*graph->nodeNum);
    if(marked == nullptr) {
        return;
    }
    for (int i = 0; i < graph->nodeNum; i++) {
        dist[i] = graph->edge[start][i];
        if (dist[i] < INF) {
            path[i] = start;
        }
        else {
            path[i] = -1;
        }
    }
    marked[start] = 1;
    //2、在dist找最小值
    int min;
    int k=0;
    for (int i = 0; i < graph->nodeNum-1; i++) {
        min = INF;
        //从未激活点中，找到最短路径
        for (int j = 0; j < graph->nodeNum; j++) {
            if (marked[j] == 0 && dist[j] < min) {
                min = dist[j];
                k=j;
            }
        }
        //此时找到最小值为min，最小下标为k
        marked[k] = 1;
        for (int j = 0; j < graph->nodeNum; j++) {
            if (marked[j] == 0&& dist[k]+graph->edge[k][j]<dist[j]) {
                dist[j] = dist[k]+graph->edge[k][j];
                path[j] = k;
            }
        }
    }
    free(marked);
}
//满递增栈
void showPath( int path[],int num,int pos) {
    int* stack = (int*)malloc(sizeof(int)*graph->nodeNum);
    if (!stack) {
        return;
    }
    int top = -1;
    while (path[pos] != -1) {
        stack[++top] = pos;
        pos = path[pos];
    }
    stack[++top] = pos;
    //出栈
    while (top != -1) {
        pos = stack[top--];
        printf("\t%d ",pos);
    }
    printf("\n");
}
